package com.hdu.other.oneDimensionPreInfo;

import java.util.HashMap;
import java.util.Map;

public class lc1590 {
    class Solution {
        public int minSubarray(int[] nums, int p) {
            int totalMod = 0;
            for (int num : nums)
                totalMod = (totalMod + num) % p;
            if (totalMod == 0)
                return 0;
            Map<Integer, Integer> mod2lastIndex = new HashMap<>();
            mod2lastIndex.put(0, -1);
            int curMod = 0;
            int ans = nums.length;
            for (int i = 0; i < nums.length; i++) {
                curMod = (curMod + nums[i]) % p;
                int find = (curMod >= totalMod) ? (curMod - totalMod) : (curMod + p - totalMod);
                if (mod2lastIndex.containsKey(find)) {
                    ans = Math.min(ans, i - mod2lastIndex.get(find));
                }
                mod2lastIndex.put(curMod, i);
            }
            return ans == nums.length ? -1 : ans;
        }
    }
}
